package com.yulongtian.offers.day202211.day20221104;


/**
 * https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/submissions/
 * 可
 *
 * @author yulongTian
 * @create 2022-11-04 15:26
 */
public class Test01 {
    public static void main(String[] args) {
        System.out.println(myPow(-1.0, -2147483648));
    }

    //快速幂实现
//    double res = 1.0;
//    int t = n;
//        while(n)
//    {
//        if(n&1) res *= x;
//        x *= x;
//        n /= 2;
//    }
//        return t > 0? res : 1.0 / res;

    public static double myPow(double x, int n) {
        //1的n次幂都是1
        if (isInt(x) && (int) x == 1) {
            return x;
        }
        //x的0次幂都是1
        if (n == 0) {
            return 1.0;
        }

        boolean flag = false;

        if (n < 0) {

            if (n == -2147483648) {
                flag = true;
                x = 1.0 / x;
                n = (n + 1) * -1;
            } else {
                x = 1.0 / x;
                n *= -1;
            }

        }

        if (isInt(x) && (int) x == -1) {
            //偶数
            if ((n & 1) == 0) {
                return 1.0;
            } else {
                if (flag) {
                    return 1.0;
                }
                return -1.0;
            }
        }

        double res = 1.0;
        String binaryString = Integer.toBinaryString(n);
        int len = binaryString.length();
        for (int i = 0; i < len; i++) {
            if (binaryString.charAt(len - i - 1) == '1') {
                res *= diGui(x, 1, (int) Math.pow(2, i));
            }
        }

        if (flag) {
            return res * (1.0 / x);
        }
        return res;
    }

    public static double diGui(double x, int current_n, int target_n) {
        if (current_n == target_n) {
            return x;
        }
        return diGui(x * x, current_n * 2, target_n);
    }


    public static boolean isInt(double num) {
        return Math.abs(num - Math.round(num)) < Double.MIN_VALUE;
    }

}
